package leaderus.study;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class PersonLimitMNByHeapSort {
	public static void main(String[] args) {  
        String tableFile=GenRandomersonDBFile.path + "//"+ GenRandomersonDBFile.fileName;
        PersonLimitMNByHeapSort personLimitMNByHeapSort = new PersonLimitMNByHeapSort();
		int[] intArray=personLimitMNByHeapSort.loadSortArray(tableFile);
		long startTime=System.currentTimeMillis();
        personLimitMNByHeapSort.heapSort(intArray);  
        System.out.println("堆排序耗时："+(System.currentTimeMillis()-startTime)+"ms");
		/*for(int i=900000;i<900100;i++){
			System.out.println(intArray[i]);
		}*/
    }  

    public void heapSort(int[] array) {  
        if (array == null || array.length <= 1) {  
            return;  
        }  

        buildMaxHeap(array);  

        for (int i = array.length - 1; i >= 1; i--) {  
            swap(array, 0, i);  

            maxHeap(array, i, 0);  
        }  
    }  

    public void buildMaxHeap(int[] array) {  
        if (array == null || array.length <= 1) {  
            return;  
        }  

        int half = array.length / 2;  
        for (int i = half; i >= 0; i--) {  
            maxHeap(array, array.length, i);  
        }  
    }  

    public void maxHeap(int[] array, int heapSize, int index) {  
        int left = index * 2 + 1;  
        int right = index * 2 + 2;  

        int largest = index;  
        if (left < heapSize && array[left] > array[index]) {  
            largest = left;  
        }  

        if (right < heapSize && array[right] > array[largest]) {  
            largest = right;  
        }  

        if (index != largest) {  
            swap(array, index, largest);  

            maxHeap(array, heapSize, largest);  
        }  
    }  
    
    public void swap(int[] array,int i,int j){
    	int tmp=array[i];
    	array[i]=array[j];
    	array[j]=tmp;
    }
    public int[] loadSortArray(String fileName){
		File personFile=new File(fileName);
		int[] sortArray=new int[1000000];
		if (personFile.exists() && personFile.isFile()) {
			try {
				InputStreamReader read = new InputStreamReader(new FileInputStream(personFile));
				BufferedReader bufferedReader = new BufferedReader(read);
				String infoLine;
				String[] infos;
				int i=0;
				while ((infoLine = bufferedReader.readLine()) != null) {
					infos = infoLine.split(",");
					sortArray[i]=Integer.valueOf(infos[0]);
					i++;
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
		}else{
			System.out.println("找不到指定文件！");
		}
		return sortArray;
	}
    
}
